package com.peng.leetcode.tree;

import java.util.HashSet;
import java.util.Set;

/**
 * HasPathSum
 * 112. 路径总和
 * https://leetcode.cn/problems/path-sum/
 * <p>
 * Created on 2022/11/29
 *
 * @author lupeng
 */
public class HasPathSum {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        dfs(root, 0);
        return sumSet.contains(targetSum);
    }

    Set<Integer> sumSet = new HashSet<>();

    void dfs(TreeNode n, int sum) {
        if (n == null) {
            return;
        }
        sum += n.val;
        if (n.left == null && n.right == null) {
            sumSet.add(sum);
        }
        dfs(n.left, sum);
        dfs(n.right, sum);
    }
}
